/**
 * @file 007.数组中和为0的三个数.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-07
 *
 * @copyright Copyright (c) 2021
 *
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        int n = nums.size();
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (int i = 0; i < n; ++i) {
            int a = nums[i];
            // 去重
            if (i != 0 && a == nums[i - 1]) {
                continue;
            }
            int j = i + 1, k = n - 1;
            while (j < k) {
                int b = nums[j], c = nums[k];
                // 去重
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    ++j;
                    continue;
                }
                if (k != n - 1 && nums[k] == nums[k + 1]) {
                    --k;
                    continue;
                }
                if (a + b + c == 0) {
                    res.push_back({nums[i], nums[j], nums[k]});
                    ++j, --k; // 别忘了找到答案，依然移动指针
                } else if (a + b + c < 0) {
                    ++j;
                } else {
                    --k;
                }
            }
        }
        return res;
    }
};

int main()
{
    vector<int> nums1 = {-1, 0, 1, 2, 0, -1, 4};
    vector<int> nums2;
    vector<int> nums3 = {0};
    vector<vector<int>> res1 = Solution().threeSum(nums1);
    for (auto &r : res1) {
        print(r);
    }
    vector<vector<int>> res2 = Solution().threeSum(nums2);
    for (auto &r : res2) {
        print(r);
    }
    vector<vector<int>> res3 = Solution().threeSum(nums3);
    for (auto &r : res3) {
        print(r);
    }
    return 0;
}